#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> ans;
vector<int> track;
int bucket;

void dfs(int start, vector<int>& candidates, int target){
    if(bucket == target){
        ans.push_back(track);
        return;
    }
    for(int i=start;i<candidates.size();i++){
        if(candidates[i] > target - bucket) continue;
        int last = i;
        while(last+1 < candidates.size() && candidates[last] == candidates[last+1]) last++;
        for(int j = 1;j<=last-i+1;j++){
            bucket += j * candidates[i];
            for(int k=0;k<j;k++) track.push_back(candidates[i]);
            dfs(last+1, candidates, target);
            bucket -= j * candidates[i];
            for(int k=0;k<j;k++) track.pop_back();
        }
        i = last;
    }
    return;
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end(), [](int a, int b){
        return a > b;
    });
    dfs(0, candidates, target);
    return ans;
}